Subject: New Chapter 8 (Pacing/Flow Control), DLSW Editor's version 0.14

From: "Alan K. Bartky, Manager of Technology" <[email-masked]>
Date: Fri, 7 Oct 94 09:06:25 PDT

----------
X-Sun-Data-Type: text
X-Sun-Data-Description: text
X-Sun-Data-Name: text
X-Sun-Content-Lines: 2
X-Sun-Content-Length: 69

Here is the promised Chapter 8 from Editor's version 0.14 of DLSw

----------
X-Sun-Data-Type: default
X-Sun-Data-Description: default
X-Sun-Data-Name: chap8.txt
X-Sun-Content-Lines: 745
X-Sun-Content-Length: 22445



RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

8. Pacing/Flow Control:

   This section describes the required Pacing and Flow Control mechanisms
   used be a Data Link Switch.

   While it is beyond the scope of this document to specify a policy for
   how an implementation maps SSP flow control to the native data link flow
   control at the edges, the following paragraphs describe a general
   philosophical overview of how the mechanism is to be applied.

   There are two types of flows which are covered by the flow control
   mechanism: connection-oriented and connectionless.  In the first,
   connection-oriented flows, the implementor is to map the native flow
   control mechanism of the two data links at the boundaries to the SSP
   flow control mechanism thus presenting an end-to-end flow control
   mechanism which "pushes back" all the way to the
   originating station in either direction.

   However, in the case of connectionless traffic, this is not possible at
   the data link level because there is no native flow control mechanism
   for connectionless data links.  At first glance it is tempting to allow
   connectionless traffic to flow the DLSw cloud unthrottled.  However, the
   rationale for subjecting these flows to flow control within the DLSw
   cloud is to "push" the discarding of frames (should this become
   necessary) back to the ingress of the DLSw cloud.  This "early
   discarding" of excessive DATAGRAMs should allow the cloud to remain
   deterministic without wasting network bandwidth.

8.1. Basic Overview

   Each session consists of two data flows, one in each direction.  Each
   data flow has its own independent flow control mechanism.  For each data
   flow there is an entity that originates traffic, referred to as the
   sender, and a target entity which receives the traffic, referred to as
   the receiver.

   A sender may only send data when its receiver has granted explicit
   permission to send a discreet number of data units.  Data units are
   defined as either a DGRMFRAME or an INFOFRAME.

   The receiver grants permission to send data units by sending a Flow
   Control Indicator (FCIND- defined later).  The sender must acknowledge
   all FCINDs by sending a Flow Control Acknowledgment (FCACK- defined
   later).

   A sending implementation must maintain these values:

     1.  GrantedUnits - The number of units (frames) which the sender
     currently has permission to send.

     2.  CurrentWindow - This is a discreet number of units, controlled by
     the receiver, which is basis for granting additional units.

AIW DLSw Related Interest Group                              [Page 78]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

     3.  InitialWindowSize - Global for all circuits on a transport
     connection.  Learned in capabilities exchange when the transport
     connection is established.  It specifies an initial value for
     CurrentWindow when each circuit is established.

   A receiving implementation must maintain these values:

     1.  CurrentWindow - This is a discreet number of units, controlled by
     the receiver, which is basis for granting additional units.

     2.  InitialWindowSize - Global for all circuits on a transport
     connection.  Sent in capabilities exchange when the transport
     connection is established.  It specifies an initial value for
     CurrentWindow when each circuit is established.

     3.  FCACKOwed - The sender owes an FCACK.  If true, no FCIND may be
     sent.

8.2. Frame Format

   The Flow control Byte is contained at offset 15 in both the Information
   and Control SSP messages.  From a flow control perspective, the flow
   control information in the two frames are handled identically.

   The following diagram describes the format of the Flow Control Byte (Bit
   7 is the most significant and Bit 0 is the Least significant bit of the
   octet):

      bit   7   6   5   4   3   2   1   0
          +---+---+---+---+---+---+---+---+
          |FCI FCA| reserved  |    FCO    |
          +---+---+---+---+---+---+---+---+

      FCI : Flow Control Indicator
      FCA : Flow Control Ack
      FCO : Flow Control Operator Bits

            000 - Repeat Window Operator
            001 - Increment Window Operator
            010 - Decrement Window Operator
            011 - Reset Window Operator
            100 - Halve Window Operator
            101 - Reserved
            110 - Reserved
            111 - Reserved

   A frame with the FCI bit set is referred to as a Flow Control Indication
   (FCIND).  An FCIND is used to manage the flow in the opposite direction
   of the frame which bears it.

   A frame with the FCA bit set is referred to as a Flow Control
   Acknowledgment (FCACK).  An FCACK is used to manage the flow in the same
   direction of the frame which bears it.

AIW DLSw Related Interest Group                              [Page 79]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

   NOTE:  A frame may be both a FCIND and an FCACK.

   A frame bearing an FCIND or FCACK may also contain data for the flow in
   the direction it is traveling.  In such a frame, the FCIND or FCACK are
   said to be piggy-backed.  A non-piggy-backed FCIND is called an
   Independent Flow Control Indication (IFCIND) and a non-piggy-backed
   FCACK is called an Independent Flow Control Acknowledgment (IFCACK).
   IFCIND and IFCACK messages are sent in a Independent Flow Control SSP
   message (type 0x21).

   NOTE:  A frame may be both an IFCIND and an IFCACK.

   It is desirable to carry information in control messages so as to reduce
   the need to send a flow control only message.  The diagram below shows
   the messages that may carry valid flow control information:

AIW DLSw Related Interest Group                              [Page 80]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

    ======                            ___                           ======
    |    |        ---------        __/   \__       ---------        |    |
    |    |      __|  _|_  |__     /   IP    \    __|  _|_  |__      |    |
    ======        |   |   |      <  Network  >     |   |   |        ======
   /______\       ---------       \__     __/      ---------       /______\
    Origin       Origin DLSw         \___/        Target DLSw      Target
    Station        partner                          partner        Station

   May have valid
    FCI/FCA/FCO    Data carrying

         Y*            N          CANUREACH_cs
                                  ----------->
         Y             N            ICANREACH_cs
                                    <-----------
         Y             N          REACH_ACK
                                  ----------->
         Y             Y            XIDFRAMEs
                                  <------------>
         Y             Y            DGRMFRAMEs
                                  <------------>
         Y             N          CONTACT
                                  ----------->
         Y             N               CONTACTED
                                    <-----------
         Y             Y             IFRAMEs
                                  <------------>
         Y             N          RESTART_DL
                                  ----------->
         Y             N               DL_RESTARTED
                                    <-----------
         Y             N          CONTACT
                                  ----------->
         Y             N               CONTACTED
                                    <-----------
         N             N          HALT_DL
                                  ----------->
         N             N               DL_HALTED
                                    <-----------

   *Note: CANUREACH_cs cannot carry FCA, as there could not be an
   outstanding
       FCI.

8.3. Granting Permission to Send Data

   A receiver grants a sender permission to send units of data by sending
   FCIND.  Each FCIND is further qualified by a flow control operator,
   which is encoded in the FCO bits of the FCIND header. With one exception
   (the Reset Window operator) all operators may be either piggy-backed or
   carried in a IFCIND.

   The five flow control operators are outlined below:

AIW DLSw Related Interest Group                              [Page 81]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

8.3.1. Repeat Window Operator

   This operator is processed as follows:

   (CurrentWindow unchanged)
   GrantedUnits += CurrentWindow

8.3.2. Increment Window Operator

   This operator is processed as follows:

             CurrentWindow++
             GrantedUnits += CurrentWindow

8.3.3. Decrement Window Operator

   This operator is processed as follows:

             CurrentWindow--
             GrantedUnits += CurrentWindow

   NOTE:  This operator may only be sent if CurrentWindow is greater than
   one.

8.3.4. Reset Window Operator

   This operator is processed as follows:

             CurrentWindow = 0;
             GrantedUnits  = 0;

   NOTE:  This operator may only flow on an independent pacing indication
   (may NOT be piggy-backed).

   NOTE:  After sending this operator, the only legal subsequent operator
   is Increment Window.

8.3.5. Halve Window Operator

   This operator shall be processed as follows:

                IF CurrentWindow > 1 THEN
                   CurrentWindow = CurrentWindow / 2
                ENDIF
                GrantedUnits += CurrentWindow

   EDITOR'S NOTE:  WE HAVE DEFINED THIS OPERATOR, BUT THERE IS NO TEXT OR
   PSEUDO-CODE INDCATING HOW TO USE THIS.

8.4. Acknowledging a Flow Control Operator

AIW DLSw Related Interest Group                              [Page 82]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

   Each sender must acknowledge each FCIND with an FCACK which is piggy-
   backed on the next frame in the opposite direction in all cases except
   the Reset Window Operator.

   The receiver may have no more than one unacknowledged FCIND outstanding
   at any time with one exception:  A Reset Window Operator may be sent
   while another FCIND is pending acknowledgment.

   NOTE: The FCI and FCO bits of the FCACK are used independently by the
   flow in the opposite direction

8.4.1. Acknowledging a Reset Window Operator

   Since this operator revokes all previously granted units, the sender
   must acknowledge this FCIND using an IFCACK (Independent Flow Control
   Acknowledgment).  This is the only case where IFCACK is used.

   Should a sender receive a non-reset FCIND followed by a Reset Window
   FCIND before acknowledging the first, it only acknowledges the Reset
   Window.

   NOTE: The FCI and FCO bits on these frames are used independently by the
   flow in the opposite direction.

8.5. Capabilities Exchange Initial Window Size

   When two nodes establish a transport connection, they engage in a
   capabilities exchange (this is a requirement).  Refer to the
   Capabilities Exchange section 7 for further details.  The two nodes are
   required to exchange the following parameter:

   InitialWindowSize -  This indicates to the partner what the sending
                        flow entity initializes its CurrentWindow
                        value to for each multiplexed session subsequently
                        established on that transport connection.  This
                        value must be non-zero.

8.6. Session Startup

   Process as follows:

          CurrentWindow = InitialWindowSize
          GrantedUnits  = 0

   NOTE: The InitialWindow Size variable has a scope of one per DLSw
   transport connection, while CurrentWindow and Granted units are
   maintained on a per circuit basis.  At session startup, a sender may not
   send data units until the receiver grants explicit permission with an
   FCIND message.  This grant may be an independent FCIND message or the
   FCIND may be piggy-backed on any of the following message types (to
   reduce the startup flows):

               CANUREACH_cs
               ICANREACH_cs

AIW DLSw Related Interest Group                              [Page 83]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

               REACH_ACK
               XIDFRAMEs
               DGRAMFRAMEs
               CONTACT
               CONTACTED

8.7. Example Receiving Implementations

   The following two examples illustrate receiving implementations of
   varying degrees of complexity.  These are not meant to be complete
   implementations but rather serve to illustrate the protocol.

   NOTE: The examples are independent of the buffering model ( buffers may
   be deterministicly or statistically committed)

   NOTE: The examples assume a process model where each event processes to
   completion without being preempted by another event.

8.7.1. Fixed Pacing Example

   Consider the following variables, in addition to InitialWindowSize and
   CurrentWindow and FCACKOwed:

      GrantDelayed     - Boolean
      GrantedUnits     - Outstanding Units

   The following section describes how various events are processed in this
   example implementation:

8.7.1.1. Circuit Startup

          CurrentWindow    = InitialWindowSize
          FCACKOwed        = FALSE
          GrantDelayed     = FALSE
          GrantedUnits     = 0
          Repeat Window Operator

8.7.1.2. Check Buffers Available

          Can my implementation afford to grant CurrentWindow just now?

8.7.1.3. Buffers Become Available

          IF Check Buffers Available THEN
             Send FCIND( Repeat Window)
             GrantDelayed = FALSE
          ELSE
             Wait on buffers to become available (LIFO)
          ENDIF

8.7.1.4. Repeat Window Operator

          IF Check Buffers Available THEN
              Send FCIND( Repeat Window)

AIW DLSw Related Interest Group                              [Page 84]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

          ELSE
             GrantDelayed = TRUE
             Wait on buffers to become available (FIFO)
          ENDIF

8.7.1.5. Send FCIND( operator)

          GrantedUnits += CurrentWindow
          FCACKOwed     = TRUE
          Encode and Transmit FCIND piggybacked or as IFCIND

8.7.1.6. A Frame Arrives from Sender

          GrantedUnits--;
          IF frame is FCACK THEN
             IF FCACKOwed THEN
                FCACKOwed = FALSE
             ELSE
                Protocol Violation
             ENDIF
          ENDIF
          IF NOT GrantDelayed THEN
             IF GrantedUnits <= CurrentWindow THEN
                 IF FCACKOwed THEN
                   Protocol Violation
                 ELSE
                   Repeat Window Operator
                 ENDIF
             ENDIF
          ENDIF

8.7.2. Adaptive Pacing Example

   The following example illustrates a receiving implementation that
   adjusts the window size and granted units based on buffer availability
   and transport utilization.

   NOTE: This example ignores other factors which might compel the
   receiving implementation to adjust the window size (i.e.  Outbound queue
   length, traffic priority, ...)

   Consider the following variables, in addition to InitialWindowSize,
   CurrentWindow and FCACKOwed:

      GrantDelayed     - Boolean
      GrantedUnits     - Outstanding Units

8.7.2.1. Circuit Startup

          CurrentWindow    = InitialWindowSize
          FCACK            = FALSE
          GrantDelayed     = FALSE
          GrantedUnits     = 0
          Repeat Window Operator

AIW DLSw Related Interest Group                              [Page 85]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

8.7.2.2. Check Buffers Available ( X)

          Can my implementation afford to grant X units just now?

8.7.2.3. Buffers Become Available

          IF Check Buffers Available THEN
             CurrentWindow--;
             Send FCIND( Decrement Window)
             GrantDelayed = FALSE
          ELSE
             Wait on buffers to become available (LIFO)
          ENDIF

8.7.2.4. Repeat Window Operator

          IF Check Buffers Available (CurrentWindow) THEN
              Send FCIND( Repeat Window)
          ELSE
             GrantDelayed = TRUE
             Wait on buffers to become available (FIFO)
          ENDIF

8.7.2.5. Increment Window Operator

          IF Check Buffers Available ( CurrentWindow + 1) THEN
              CurrentWindow++
              Send FCIND( Increment Window)
          ELSE
              Repeat Window Operator
          ENDIF

8.7.2.6. Send FCIND( operator)

          FCACKOwed     = TRUE
          GrantedUnits += CurrentWindow
          Encode and Transmit FCIND piggybacked or as IFCIND

8.7.2.7. An FCACK Arrives from Sender

          GrantedUnits--;
          IF NOT FCACKOwed THEN
             Protocol Violation
          ENDIF
          FCACKOwed = FALSE;
          IF NOT GrantDelayed THEN
             IF GrantedUnits < CurrentWindow THEN
                 Increment Window Operator
             ELSE IF GrantedUnits == CurrentWindow THEN
                 Repeat Window Operator
             END
          ENDIF

AIW DLSw Related Interest Group                              [Page 86]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

8.7.2.8. A Non-FCACK Frame Arrives from Sender

          GrantedUnits--;
          IF NOT GrantDelayed THEN
             IF FCACKOwed THEN
                IF GrantedUnits < CurrentWindow THEN
                   Protocol Violation
                END
             ELSE
                IF GrantedUnits <= CurrentWindow THEN
                   Repeat Window Operator
                ENDIF
             ENDIF
          ENDIF

AIW DLSw Related Interest Group                              [Page 87]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

8.7.2.9. Example Flows from the Above Implementation

   -----SENDER-----                     ----RECEIVER----
   Granted   Window                     Window   Granted
     0         2   circuit established    2         0
     2         2   <-------- FCIND(Rpt)   2         2
     1         2   FCACK-------------->   2         1
     4         3   <-------- FCIND(Inc)   3         4
     3         3   FCACK-------------->   3         3
                          +- FCIND(Rpt)   3         6
     2         3   DATA---|----------->   3         5
     1         3   DATA---|----------->   3         4
     4         3   <------+
     3         3   FCACK-------------->   3         3
     6         3   <-------- FCIND(Rpt)   3         6
     5         3   FCACK-------------->   3         5
     4         3   DATA--------------->   3         4
     3         3   DATA--------------->   3         3
                          +- FCIND(Rpt)   3         6
     2         3   DATA---|----------->   3         5
     1         3   DATA---|----------->   3         4
     0         3   DATA---|----------->   3         3
     3         3   <------+
     2         3   FCACK-------------->   3         2
     6         4   <-------- FCIND(Inc)   4         6
     5         4   FCACK-------------->   4         5
     4         4   DATA--------------->   4         4
                                        Waiting on Buffer
                          +- FCIND(Dec)   3         7
     3         4   DATA---|----------->   3         6
     2         4   DATA---|----------->   3         5
     1         4   DATA---|----------->   3         4
     0         4   DATA---|----------->   3         3
     3         3   <------+
     2         3   FCACK-------------->   3         2
                                        Waiting on Buffer
                          +- FCIND(Dec)   2         4
     1         3   DATA---|----------->   2         3
     0         3   DATA---|----------->   2         2
     2         2   <------+
     1         2   FCACK-------------->   2         1
     4         3   <-------- FCIND(Inc)   3         4
     3         3   FCACK-------------->   3         3
     6         3   <-------- FCIND(Rpt)   3         6
     5         3   FCACK-------------->   3         5
     4         3   DATA--------------->   3         4
     3         3   DATA--------------->   3         3
     6         3   <-------- FCIND(Rpt)   3         6

AIW DLSw Related Interest Group                              [Page 88]

RFC XXXX      DLSw: Switch-to-Switch Protocol              August 1994

8.8. Other Considerations

8.8.1. Protocol Violations

   The following events is considered protocol violations:

   1.  Sender exceeds granted units or does not acknowledge FCIND on first
   frame after its receipt (the receiver can not discern the difference
   between the two).

   2.  Receiver does not follow a Reset Window Operator with an Increment
   Window Operator.

   3.  Receiver has two unacknowledged FCINDs ( other than Reset Window)
   outstanding.

   4.  Receiver sends Decrement Window Operator with a window size of one.

   Actions taken in response to protocol violations are left to the
   implementation of the node which discovers the violation.  If an
   implementation chooses to take down the circuit on which the violation
   occurred, HALT_DL is the appropriate action.

AIW DLSw Related Interest Group                              [Page 89]